package com.zklh.leetcode.tree.middle;

import com.zklh.leetcode.tree.model.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author ：tong nan
 * @date ：Created in 2021/4/28 17:48
 * @description ：查找重复的子树
 * @modifiedBy ：
 */
public class RepeatTreeFinder {

    // 用于填所有结点展开的值
    private Map<String,Integer> nodeRepeatMap = new HashMap<>();
    private List<TreeNode> result = new ArrayList<>();

    // 寻找重复的子树
    public List<TreeNode> find(TreeNode root) {

        spread(root);
        return result;
    }

    /**
     * 返回当前结点展开的结果,
     * @param root
     * @return
     */
    public String spread(TreeNode root) {

        if (root == null) {
            return "";
        }
        String spreadStr = spread(root.left) +"#"+ root.val+ "#"+spread(root.right);
        if (nodeRepeatMap.containsKey(spreadStr)) {
            if (nodeRepeatMap.get(spreadStr) == 1) {
                result.add(root);
            }
            nodeRepeatMap.put(spreadStr, nodeRepeatMap.get(spreadStr)+1);
        } else {
            nodeRepeatMap.put(spreadStr,1);
        }
        return spreadStr;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(4);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(2);
        root.right.left.left = new TreeNode(4);
        root.right.right = new TreeNode(3);

        RepeatTreeFinder repeatTreeFinder = new RepeatTreeFinder();
        List<TreeNode> result  = repeatTreeFinder.find(root);

    }

}
